#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * TODO: 该文件代码后续重写
 *  https://www.bilibili.com/video/BV1MK411j7CR/?vd_source=414fd381c40fd85cbec992fd7202bf29
 * 
*/



#define leaf_node_num 8                        // 叶子结点数
#define node_total_num (2 * leaf_node_num - 1) // 哈夫曼树中的结点总数
#define MAX_WEIGHT 10000                       // 定义一个相对于权值很大的值

// --------------------哈夫曼树--------------------
// 定义哈夫曼结点的存储结构
typedef struct htnode
{
    char name;    // 定义该结点的名字
    int lchild;   // 左孩子
    int rchild;   // 左孩子
    float weight; // 权值
    int parent;   // 双亲指针
} HTNode;         // 树中结点类型

// 方式①: 哈夫曼树数组
typedef HTNode HuffmanTree[node_total_num + 1]; // 0 号单元不可用

// 方式②: 哈夫曼树结构体
typedef struct phuffmantree
{
    int num;     // 结点数
    int root;    // 哈夫曼根结点
    HTNode *htn; // 指向哈夫曼树指针
} *PHuffmanTree;

// --------------------哈夫曼编码--------------------
// 定义哈夫曼编码结构
typedef struct
{
    char ch;                      // 存放编码的字符
    char bits[leaf_node_num + 1]; // 存放编码位串
    int len;                      // 编码长度
} CodeNode;

typedef CodeNode HuffmanCode[leaf_node_num + 1]; // 0 号单元不可用

// BUG: 以下的操作有些问题暂时先这样


// ---------------------哈夫曼树--PHuffmanTree-----------------------------
// 该函数用于打印哈夫曼树的所有结点
void printPHuffmanTree(PHuffmanTree pht, int num)
{
    // printf() 
    for (int i = 0; i < 2 * num - 1; i++)
    {
        printf("第%d个结点: weight=%f parent=%d lchild=%c rchild=%c\n",
               i, pht->htn[i].weight, pht->htn[i].parent, pht->htn[i].lchild, pht->htn[i].rchild);
    }
}

PHuffmanTree createPHuffmanTree(int n, int w[], char data[])
{
    int totalNodeNum = 2 * n - 1;

    PHuffmanTree pht = (PHuffmanTree)malloc(sizeof(HTNode));
    if (pht == NULL)
    {
        printf("pht malloc Out of space!\n");
        return pht;
    }

    pht->root = totalNodeNum - 1; // 根节点位置
    pht->num = n;                 // 哈夫曼树的叶子结点数

    // 为哈夫曼树分配2n-1个结点空间
    pht->htn = (HTNode *)malloc(totalNodeNum * sizeof(HTNode));
    if (pht->htn == NULL)
    {
        printf("htn malloc Out of space!\n");
        return pht;
    }

    // 初始化哈夫曼树
    for (int i = 0; i < totalNodeNum; i++)
    {
        pht->htn[i].lchild = -1; // 初始化叶结点左孩子
        pht->htn[i].rchild = -1; // 初始化叶结点右孩子
        pht->htn[i].parent = -1; // 初始化叶结点的父结点

        if (i < n)
        {
            pht->htn[i].weight = w[i];  // 赋值叶子结点的权值
            pht->htn[i].name = data[i]; // 初始化叶子结点的data
        }
        else
        {
            pht->htn[i].weight = -1; // 初始化内部结点的权值为-1
        }
    }

    int index, subIndex; // 定义最小值下标、次小值下标
    int min, subMin;     // 最小值、次小值
    // 构造内部结点
    for (int i = 0; i < n - 1; i++)
    {
        min = 100;    // 初始化最小值为100
        subMin = 100; // 初始化次小值为100

        index = -1;    // 初始化最小值下标为-1
        subIndex = -1; // 初始化次小值下标为-1

        for (int j = 0; j < n + i; j++)
        {
            // 找到最小值下标赋值给x1,最小值赋值给min1
            if (pht->htn[j].weight < min && pht->htn[j].parent == -1)
            {
                subMin = min;
                subIndex = index;
                min = pht->htn[j].weight;
                index = j;
            }
            // 找到次小值下标赋值给x2,最次值赋值给 subMin
            else if (pht->htn[j].weight < subMin && pht->htn[j].parent == -1)
            {
                subMin = pht->htn[j].weight;
                subIndex = j;
            }
        }

        pht->htn[n + i].lchild = index;        // 给父结点左孩子赋值
        pht->htn[n + i].weight = min + subMin; // 初始化父结点的权值
        pht->htn[n + i].rchild = subIndex;     // 给父结点右孩子赋值
        pht->htn[index].parent = n + i;        // 给左孩子的父结点赋值
        pht->htn[subIndex].parent = n + i;     // 给右孩子的父结点赋值
    }

    return pht;
}

char *inputNodeName(int len)
{
    char *data;
    // 依次输入结点的名称，不需要加空格
    for (int i = 0; i < len; i++)
    {
        scanf("%c", &data[i]);
        printf("-->%c\n", data[i]);
    }
    return data;
}

int *inputNodeWeight(int len)
{
    int *weight;
    // 依次输入结点的权值. 加空格连续输入
    for (int i = 0; i < len; i++)
    {
        scanf("%d", &weight[i]);
        printf("-->%d\n", weight[i]);
    }
    return weight;
}

// ---------------------哈夫曼树--HuffmanTree-----------------------------
// 选出两个最小权值的根结点
void select(HuffmanTree T, int k, int *s1, int *s2)
{
    // 从哈夫曼树中选择parent为0 且权值最小的两个根结点。其序号分别存储到 s1 和 s2 指向的对应变量中
    int i, j;
    int min1 = 101;
    for (i = 0; i <= k; i++)
    {
        if (T[i].weight < min1 && T[i].parent == 0)
        {
            j = i;
            min1 = T[i].weight;
        }
    }

    (*s1) = j;
    min1 = 32767;

    for (i = 1; i <= k; i++)
    {
        if (T[i].weight < min1 && T[i].parent == 0 && i != (*s1))
        {
            j = i;
            min1 = T[i].weight;
        }
    }

    (*s2) = j;
}

void chuffmanTrees(HuffmanTree HT)
{
    int s1, s2;

    for (int i = 1; i <= node_total_num; i++)
    {
        HT[i].lchild = 0;
        HT[i].rchild = 0;
        HT[i].parent = 0;
        HT[i].weight = 0;
    }

    for (int i = 1; i <= leaf_node_num; i++)
    {
        float www = HT[i].weight;
        // 输入前 n 个叶结点的权值
        // scanf("%f", &www);
        printf("input--->i=%d, %f\n", i, www);
        // 在 HT[1..i-1] 中选择parent为0且权值最小的两根结点
        // for (i = leaf_node_num + 1; i <= node_total_num; i++)
        // {
        //     // select(HT, i - 1, &s1, &s2);
        // }
        printf("+++%d\n", __LINE__);
        // HT[s1].parent = i;
        // HT[s2].parent = i;
        printf("+++%d\n", __LINE__);
        // HT[i].lchild = s1;
        // HT[i].rchild = s2;
        // 权值之和
        printf("+++%d\n", __LINE__);
        // HT[i].weight = HT[s1].weight + HT[s2].weight;
        //  printf("+++%d\n", __LINE__);
    }
}

void printTree(HuffmanTree HT)
{
    for (int i = 0; i < node_total_num; i++)
    {
        HTNode node = HT[i];
        printf("第%d个结点: weight=%f parent=%d leftchild=%c rightchild=%c\n", i,
               node.weight, node.parent, node.lchild, node.rchild);
    }
}

// 求哈夫曼编码
void huffmanEncoding(HuffmanTree HT, HuffmanCode HC)
{
    int c, p, i;
    char cd[leaf_node_num + 1];
    cd[leaf_node_num] = '\0';

    int start;
    for (i = 1; i <= leaf_node_num; i++)
    {
        start = leaf_node_num;
        c = i;
        while (p == HT[c].parent > 0)
        {
            cd[--start] = (HT[p].lchild == c) ? '1' : '0';
            c = p;
        }

        strcpy(HC[i].bits, &cd[start]);
        HC[i].len = leaf_node_num - start;
    }
}

int main()
{
    int nodenums = 8;
    printf(">>input names: ");
    char *names = inputNodeName(nodenums);
    printf("\n>>input weights: ");
    int *weights = inputNodeWeight(nodenums);
    printf("\n------------create huffman tree----------");
    PHuffmanTree p = createPHuffmanTree(nodenums, weights, names);
    printf("\n------------print huffman tree----------\n");
    printPHuffmanTree(p, nodenums);
    printf("\n");
    return 0;
}